package cn.handong.tool.algorithm.查找;


import javax.persistence.Id;

public class 二维数组查找 {
    // 单行递增二维数组查找
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] > target){
                break;
            }
            if (matrix[i][matrix[0].length - 1] < target){
                continue;
            }
            int col = binarySearch(matrix[i],target);
            if (col != -1){
                return true;
            }
        }
        return false;
    }

    public int binarySearch(int[] nums, int target){
        int start = 0;
        int end = nums.length - 1;
        while (start <= end){
            int mid = (start + end) >>> 1;
            if (nums[mid] == target){
                return mid;
            }else if (nums[mid] < target){
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        return -1;
    }


    // 严格递增二维数组查找
    public boolean searchMatrix2(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix,target);
        if (rowIndex < 0){
            return false;
        }
        return binarySearchRow(matrix[rowIndex],target);
    }

    private boolean binarySearchRow(int[] matrix, int target) {
        int low = 0, high = matrix.length - 1;
        while (low < high){
            int mid = (low + high) >>> 1;
            if (matrix[mid] == target){
                return true;
            }else if (matrix[mid] > target){
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        return false;
    }

    private int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high){
            int mid = (low + high) >>> 1;
            if (matrix[mid][0] <= target){
                low = mid;
            }else {
                high = mid - 1;
            }
        }
        return low;
    }

}
